package com.wzw.basics.sort;

import java.util.Arrays;

/**
 * @author Wangzhiwen
 */
public class QuickSort {

/*    public static int[] execute(int[] arrays, int start, int end) {
        if (start < 0 || end >= arrays.length || start > end) {
            return null;
        }
        int smallIndex = partition(arrays, start, end);
        if (smallIndex > start) {
            execute(arrays, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            execute(arrays, smallIndex + 1, end);
        }
        return arrays;
    }

    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
//        int pivot = (end - start) / 2;
        int smallIndex = start - 1;
        // arrays[end] 为基准值
        swap(array, pivot, end);
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        return smallIndex;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }*/

    public static void execute(int[] arrays) {
        int len;
        if (arrays == null || (len = arrays.length) == 0 || len == 1) {
            return;
        }
        sort(arrays, 0, len - 1);
        System.out.println("quick sort " + Arrays.toString(arrays));
    }

    public static void sort(int[] array, int left, int right) {
        if (left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while (i != j) {
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while (array[j] >= base && i < j) {
                j--;
            }

            // 再从左往右边找，直到找到比base值大的数
            while (array[i] <= base && i < j) {
                i++;
            }

            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }

}
